package com.sun;

/**
 * https://leetcode.cn/problems/swap-nodes-in-pairs/
 * 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。
 * 你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）
 */
public class Test24两两交换链表中的节点 {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
//        listNode3.next = listNode4;
        ListNode listNode = swapPairs1(listNode1);
        printList(listNode);

    }

    /**
     *方法一：自己
     */
    public static ListNode swapPairs1(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        ListNode res = head.next;
        ListNode second = new ListNode();
        ListNode temp = new ListNode();
        while (head != null && second != null && head.next != null){
            second = head.next;
            head.next = second.next;
            second.next = head;
            temp.next = second;
            temp = head;
            head = head.next;
        }
        return res;
    }

    /**
     *方法2：力扣官方
     */
    public static ListNode swapPairs2(ListNode head) {
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode temp = pre;
        while (temp.next != null && temp.next.next != null) {
            ListNode start = temp.next;
            ListNode end = temp.next.next;
            temp.next = end;
            start.next = end.next;
            end.next = start;
            temp = start;
        }
        return pre.next;
    }

    /**
     * 方法3：力扣官方递归
     */
    public static ListNode swapPairs3(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode next = head.next;
        head.next = swapPairs3(next.next);
        next.next = head;
        return next;
    }

    public static void printList(ListNode listNode){
        while (listNode != null){
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }
}
